In certain video or film image processing systems, the image rate (number of images per second) is insufficient for high-quality display. Consequently, additional images are generated via an interpolation function and displayed between original images in order to increase the image rate and improve the quality of the display. An interpolation function of this type conventionally calculates the value of the pixels of an interpolated image, in particular as a function of the value of the pixels of the preceding original image and/or the value of the pixels of the following original image.
Such an interpolation function is based on the correlation that exists between successive images of a video or film. This is because, in a sequence of video images, subjects that are moving generally appear in different respective regions of several consecutive images. Interpolated images are therefore generated from parts of preceding and/or following original images.
Conventionally, an image is divided into pixel blocks and the assumption is made that each block is substantially identical from one image to another even if there is motion of this block between two images. Consequently, an image is interpolated from original images by seeking, for each current block of the image being interpolated, that one of the blocks of a preceding original image and/or a following original image that is the most probable.
Motion estimation and/or compensation methods offer block searching methods thus adapted for generating interpolated images. A correlation between those parts of the consecutive images in which a moving object appears may in fact be expressed via a motion vector. The motion vector represents the motion of a pixel block from one image to the other. It has a vertical component and a horizontal component, representing the displacement that has to be applied to a block of a preceding image in order to arrive at the position of a substantially identical pixel block in a following image.
Such methods are conventionally used in video data compression systems, such as systems based on the MPEG standard. Such systems are used to reduce the quantity of image data to be transmitted or stored, by compressing this data so as to allow it to be rapidly transferred to digital networks or even telephone lines, or to allow it to be recorded on digital media. Consequently, only certain reference images are encoded and transmitted, and then, on the receive side, the missing intermediate images are interpolated according to the motion vectors transmitted with the encoded images.
In such systems, on the transmit side, the intermediate image is processed so as to transmit the least possible amount of information, as mentioned above. Thus, the intermediate image is divided into blocks. For each block, a correlation is calculated between the current block and a selection of candidate blocks of a preceding and/or following original or already processed image. This correlation calculation delivers an error relating to each candidate block. A candidate block is elected, in order to represent the current block of the intermediate image. The elected candidate block is that one having the highest correlation with the current block, or else the smallest error. To allow interpolation of the intermediate images on the receive side, the processed image is transmitted via the following information, which is generally transmitted relative to a current block of an image to be interpolated:                an indication of the candidate block elected;        a motion vector representing a displacement of the elected candidate block to the position of the current block; and        an error delivered by the correlation calculation.        
Thus, on the receive side, the missing processed images are interpolated on the basis of the information received with the encoded images and a value of pixels of each block of these images is thus determined.
Certain interlaced image display systems also use motion estimation and/or compensation methods.
Image rate conversion devices also employ such methods. Such devices make it possible in fact to increase an original image rate by generating additional images obtained by interpolation of the original images. These devices are conventionally used to adapt the image rates between, on the one hand, an image generation, encoding, transmission and/or storage system and, on the other hand, an image display system, which involve different image rates.
In this case, the image to be interpolated is divided into blocks. For each of the blocks, candidate vectors are generally generated. For each of the candidate vectors, a block in the preceding original image and a block in the following original image corresponding to a displacement of the position of the current block relative to the candidate vector are selected, and then the correlation between the selected block of the preceding image and the selected block of the following image is calculated. The candidate vector elected is the vector for which the calculated correlation is the largest. The current block is then interpolated from the block in the preceding original image and from the block in the following original image that are associated with the candidate vector elected. In this way, images are generated by interpolation.
The term “processed image” refers to images divided into a plurality of blocks for which a motion vector has been elected. Thus, interpolated images are generated by interpolation of the processed images.
The next section presents basic concepts conventionally used in motion estimation methods. It is common practice to distinguish several types of images: original images of type I (intra images) which are encoded without reference to other images; images of type P (predictive images) which are interpolated via a motion estimation algorithm on the basis of a preceding original image; and images of type B (bidirectional images) which are interpolated via a motion estimation algorithm based on a preceding original image and on a following original image.
In general, a motion estimation is based on the assumption that a block of pixels of the image being processed can be modeled as a displacement of a block of the preceding and/or following original image. In such a model, it is therefore assumed that each pixel of any one block of pixels undergoes substantially the same displacement. A motion vector associated with each block of pixels of a processed image represents this displacement movement. Then, by applying to each of the pixel blocks of the preceding original image and/or each of the pixel blocks of the following original image a displacement corresponding to the respective associated motion vector, each current block of the image being processed is generated from a pixel block of the preceding and/or following original image in order to obtain an interpolated image.
In motion estimation methods, the motion vector associated with the current block of pixels is elected from among a set of candidate motion vectors. In conventional methods, an error is calculated for each of the candidate motion vectors and the elected motion vector is that one among the candidate motion vectors that has the smallest calculated error, that is to say the highest correlation.
When, for a given current block, the calculated errors for at least two of the candidate motion vectors are substantially equivalent, it is difficult to elect the most suitable motion vector for this current block. However, the performance of such methods depends especially on the choice of the motion vector to be associated with the current block since the interpolated image is obtained from this information. In cases when it is difficult to elect a motion vector on the basis of the calculated error, certain methods are used to apply penalties to the calculated errors with respect to the candidate motion vectors.
Thus, motion estimation methods in which a penalty is applied to the calculated error for each candidate vector, so as to deliver a modulated error relative to the candidate vector, are known. The elected motion vector for a current block is that one, among the candidate motion vectors, that has the smallest error thus modulated.
International Application Publication No. WO 02/087210 discloses a method for calculating an error with a penalty, with the penalty depending on the position and the norm of the candidate motion vectors.